import java.util.*;

/**
 * 894. 所有可能的满二叉树
 * https://leetcode-cn.com/problems/all-possible-full-binary-trees/
 */
public class Solutions_894 {
    public static void main(String[] args) {
        List<TreeNode> result = allPossibleFBT(7);
        for (TreeNode node : result) {
            System.out.println(MyTreeNodeUtils.serialize(node));
        }
//        System.out.println(result);
    }

    // 递归中存在大量的重复子问题，可以采用记忆化的方式，减少递归的工作量
    // 比如：N = 5 时，能够生成的满二叉树，最多只有 5 种，因为可以记录下，重复使用
    public static Map<Integer, List<TreeNode>> memory = null;
    public static List<TreeNode> allPossibleFBT(int N) {
        memory = new HashMap<>();
        return recursion(N);
    }

    public static List<TreeNode> recursion(int N) {
        if (N % 2 == 0) {
            // 剪枝：偶数不可能构成满二叉树
            return new ArrayList<>();
        }
        if (memory.containsKey(N)) {
            // 剪枝：备忘录中存在
            return memory.get(N);
        }
        List<TreeNode> res = new ArrayList<>();
        if (N == 1) {
            res.add(new TreeNode());
            return res;
        }
        // 固定并循环左子节点的个数，则右子节点的个数计算产生，个数分别为 [1, 3, 5, ...，N - 2]
        for (int i = 1; i < N; i += 2) {
            // i 个节点时，递归生成所有可能的左子树列表
            List<TreeNode> leftPossible = allPossibleFBT(i);
            // N - i - 1 个节点时，递归生成所有可能的右子树列表
            // 为什么还要减 1？因为根节点也需要占用一个节点
            List<TreeNode> rightPossible = allPossibleFBT(N - i - 1);
            // 左子树 * 右子树的可能，即为能够组成的全部可能
            for (TreeNode l : leftPossible) {
                for (TreeNode r : rightPossible) {
                    TreeNode root = new TreeNode();
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        // 节点个数为 N 时，将已经计算得到的结果 res，记录到 memory 中，供其他递归使用
        memory.put(N, res);
        return res;
    }
}
